package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem/">1233. 删除子文件夹</a>
 */
private class Solution1233 {
    class Data {
        var next: HashMap<String, Data>? = HashMap()

        fun put(list: List<String>, ind: Int) {
            if (next == null) {
                return
            }
            if (ind >= list.size) {
                next = null
                return
            }
            next?.let {
                val part = list[ind]
                if (it[part] == null) {
                    val n = Data()
                    it[part] = n
                    n.put(list, ind + 1)
                } else {
                    it[part]?.put(list, ind + 1)
                }
            }
        }

        fun fill(rst: ArrayList<String>, now: String) {
            if (next == null) {
                rst.add(now)
                return
            }
            next?.let {
                for (item in it) {
                    item.value.fill(rst, "$now/${item.key}")
                }
            }
        }
    }

    fun removeSubfolders(folder: Array<String>): List<String> {
        val data = Data()
        for (item in folder) {
            data.put(item.removePrefix("/").split("/"), 0)
        }
        val rst = ArrayList<String>()
        data.fill(rst, "")
        return rst
    }
}

fun main() {
    println(Solution1233().removeSubfolders(
        arrayOf("/a","/a/b","/c/d","/c/d/e","/c/f")
    ))
}